{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Permutation LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canPermutePalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。</p>\n",
    "\n",
    "<p>回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。</p>\n",
    "\n",
    "<p>回文串不一定是字典当中的单词。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：&quot;</strong>tactcoa&quot;\n",
    "<strong>输出：</strong>true（排列有&quot;tacocat&quot;、&quot;atcocta&quot;，等等）\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-permutation-lcci](https://leetcode.cn/problems/palindrome-permutation-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-permutation-lcci](https://leetcode.cn/problems/palindrome-permutation-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"code\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            if c not in freq:\n",
    "                freq[c] = 1\n",
    "            else:\n",
    "                freq[c] += 1\n",
    "        num_odd = 0\n",
    "        for f in freq.values():\n",
    "            if f % 2 == 1:\n",
    "                num_odd += 1\n",
    "        return num_odd <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        res = 0\n",
    "        for i in set(s):\n",
    "            if s.count(i) % 2 != 0:\n",
    "                res += 1\n",
    "        if res > 1:\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        from collections import Counter\n",
    "        cnt = 0\n",
    "        for k, v in Counter(s).items():\n",
    "            if v % 2:\n",
    "                cnt += 1\n",
    "        return cnt <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return len([k for k, v in Counter(s).items() if v % 2 != 0]) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        for v in dic.values():\n",
    "            if v % 2 == 1:\n",
    "                cnt += 1\n",
    "                if cnt > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        count_odd = 0\n",
    "        for i in dic:\n",
    "            if dic[i] % 2 == 1:\n",
    "                count_odd += 1\n",
    "            if count_odd > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 偶数的话全为偶数\n",
    "        # 奇数的话一个为奇数\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]] = 1\n",
    "            else:\n",
    "                dic[s[i]] += 1\n",
    "        count = 0\n",
    "        for k,v in dic.items():\n",
    "            if v%2 != 0:\n",
    "                count += 1\n",
    "        return count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for value in dic.values():\n",
    "            if value%2==1:\n",
    "                odd+=1\n",
    "                if odd>1:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        num = 0\n",
    "        for _, val in dic.items():\n",
    "            if val % 2 == 1:\n",
    "                num += 1\n",
    "            if num > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        c = Counter(s)\n",
    "        count = 0\n",
    "\n",
    "        for value in c.values():\n",
    "            \n",
    "            if value%2 != 0:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        #idea: for a string to be palindrome permutation, it must have the      following traits: 1. there can be at most one character which only appeared odd times. ex: abcba. note if there are two characters that only made odd appearance, then it is not palindrome. ex: abcbae 2. other than that single character, all other characters will have to make even times of appearance 3. thus we use a dictionary to store the characters with single appearance, if we iterate through the entire string and the odd dictionary's key is no more than 1, that means the above two conditions have been met, and we have a palindrome permutation. else, we should return false. \n",
    "\n",
    "        odd = {}\n",
    "        for cha in s:\n",
    "            if cha in odd.keys(): #check if character is in dictionary\n",
    "                del odd[cha] #if it is, then it has appeared even times now, del it from the dict\n",
    "            else:\n",
    "                odd[cha] = 0 #if it's not, then it has appeared odd times, add to the dict\n",
    "        if len(odd) <= 1: #after traversing through the str, it dict len is no more than 1, return true, else return false\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val %2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = {}\n",
    "        for char in s:\n",
    "            if char in d:\n",
    "                d[char] += 1\n",
    "            else:\n",
    "                d[char] = 1\n",
    "        ord_c = 1\n",
    "        for key, value in d.items():\n",
    "            #if value % 2 != 0:\n",
    "            if value & 1 != 0:\n",
    "                if ord_c == 0:\n",
    "                    return False\n",
    "                ord_c -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for c in s:\n",
    "            if c in dic:\n",
    "                dic[c] += 1\n",
    "            else:\n",
    "                dic[c] = 1\n",
    "        temp = {key:value for key,value in dic.items() if value %2 ==1}\n",
    "        print(temp)\n",
    "        if len(s) % 2 ==0:\n",
    "            if len(temp)>=1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            if len(temp) == 1:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic=defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val%2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        word_dict = {}\n",
    "        for char in s:\n",
    "            word_dict[char] = word_dict.get(char, 0) + 1\n",
    "        odd_count = 0\n",
    "        for value in word_dict.values():\n",
    "            if value % 2:\n",
    "                odd_count += 1\n",
    "            if odd_count > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        if not s:return True\n",
    "\n",
    "        list1 = []\n",
    "        for key in s:\n",
    "            if key not in list1:\n",
    "                list1.append(key)\n",
    "            else:\n",
    "                list1.remove(key)\n",
    "        return True if len(list1)<2 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l1 = []\n",
    "        for i in s:\n",
    "            if i not in l1:\n",
    "                l1.append(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "                continue\n",
    "            if i in s and i in l1:\n",
    "                l1.remove(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "        return len(set(l1)) <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        h = defaultdict(int)\n",
    "        for char in s:\n",
    "            h[char] += 1\n",
    "\n",
    "        size = len(s)\n",
    "        odd_count = 0\n",
    "        for v in h.values():\n",
    "            if v % 2 != 0:\n",
    "                odd_count += 1\n",
    "\n",
    "        if odd_count > 1:\n",
    "            return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ans = []\n",
    "        for i in range(len(s)):\n",
    "            if s.count(s[i]) % 2 == 1:\n",
    "                if not ans and s[i] not in ans:\n",
    "                    ans.append(s[i])\n",
    "                elif ans and s[i] in ans:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        assist = []\n",
    "        for x in s:\n",
    "            if x in assist:\n",
    "                assist.remove(x)\n",
    "            else:\n",
    "                assist.append(x)\n",
    "        \n",
    "        return len(assist) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        hashmap = dict()\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            try:\n",
    "                hashmap[i] = not hashmap[i]\n",
    "                if hashmap[i]:\n",
    "                    res-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "            except:\n",
    "                hashmap[i] = False\n",
    "                res += 1\n",
    "        return res<2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = Counter(list(s))\n",
    "        a = 0\n",
    "        for k, v in c.items():\n",
    "            if v % 2:\n",
    "                a += 1\n",
    "            if a > 1:\n",
    "                return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        a=dict(Counter(s))\n",
    "        n,f=0,0\n",
    "    \n",
    "        for i in a.values():\n",
    "            if i%2==1:\n",
    "                f+=1\n",
    "            if f==2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canPermutePalindrome(self, s: str) -> bool:\n",
    "#         char_bitmap = [False] * 128\n",
    "#         for ch in s:\n",
    "#             pos = ord(ch)\n",
    "#             char_bitmap[pos] = not char_bitmap[pos]\n",
    "#         flag = False\n",
    "#         for i in range(128):\n",
    "#             if char_bitmap[i]:\n",
    "#                 if not flag:\n",
    "#                     flag = True\n",
    "#                 else:\n",
    "#                     return False\n",
    "#         return True\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = Counter(s)\n",
    "        t = 0\n",
    "        for key,val in dic.items():\n",
    "            if val % 2:\n",
    "                t += 1\n",
    "            if t > 1:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        one_chance = True\n",
    "        for v in cnt.values():\n",
    "            if v % 2 == 1 and one_chance:\n",
    "                one_chance = False\n",
    "            elif v % 2 == 1 and not one_chance:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        temp = set()\n",
    "        for i in s:\n",
    "            if i in temp:\n",
    "                temp.remove(i)\n",
    "            else:\n",
    "                temp.add(i)\n",
    "        if len(temp) == 0 or len(temp) == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# leetcode submit region begin(Prohibit modification and deletion)\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        char_bitmap = [False] * 128\n",
    "        for ch in s:\n",
    "            pos = ord(ch)\n",
    "            char_bitmap[pos] = not char_bitmap[pos]\n",
    "        flag = False\n",
    "        for i in range(128):\n",
    "            if char_bitmap[i]:\n",
    "                if not flag:\n",
    "                    flag = True\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "      carr = [0] * 122\n",
    "      isp = not (len(s)%2==0)\n",
    "      for car in s:\n",
    "        carr[ord(car)] += 1\n",
    "\n",
    "      for cad in carr:\n",
    "        if cad%2==0:\n",
    "          pass\n",
    "        elif isp:\n",
    "          isp = False\n",
    "        else:\n",
    "          return False\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = set()\n",
    "        for c in s:\n",
    "            if c in cnt:\n",
    "                cnt.remove(c)\n",
    "            else:\n",
    "                cnt.add(c)\n",
    "        return len(cnt) < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "                if error > 1:\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        record = set()\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in record:\n",
    "                record.add(s[i])\n",
    "            else:\n",
    "                record.remove(s[i])\n",
    "        if (len(record) == 1 and len(s) %2 != 0) or (len(record) == 0 and len(s) %2 == 0):\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l1 = []\n",
    "        for i in s:\n",
    "            if i not in l1:\n",
    "                l1.append(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "                continue\n",
    "            if i in s and i in l1:\n",
    "                l1.remove(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "        return len(set(l1)) <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        l1 = []\n",
    "        for i in s:\n",
    "            if i not in l1:\n",
    "                l1.append(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "                continue\n",
    "            if i in s and i in  l1:\n",
    "                l1.remove(i)\n",
    "                s = s.replace(i, \"\", 1)\n",
    "        return len(set(l1)) <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        return sum(1 for v in Counter(s).values() if v%2) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        res = defaultdict(int)\n",
    "        for c in s:\n",
    "            res[c] += 1\n",
    "        count = 0\n",
    "        for v in res.values():\n",
    "            if v % 2 != 0:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return count == 0 if len(s) % 2 == 0 else count == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        lst = []\n",
    "        for i in s:\n",
    "            if i not in lst:\n",
    "                lst.append(i)\n",
    "            else:\n",
    "                lst.remove(i)\n",
    "        return len(lst) == 1 or len(lst)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ans=0\n",
    "        cnt=Counter(s)\n",
    "        for i in cnt:\n",
    "            ans+=cnt[i]%2\n",
    "        return ans<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        count = 0\n",
    "        for value in dic.values():\n",
    "            if value % 2:\n",
    "                count += 1\n",
    "        if count >=2:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        result = 0\n",
    "        for c in s:\n",
    "            result ^= 1 <<ord(c)\n",
    "            print(result)\n",
    "        return result & (result-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        s_count = {}\n",
    "        for char in s:\n",
    "            if char in s_count:\n",
    "                s_count[char] += 1\n",
    "            else:\n",
    "                s_count[char] = 1\n",
    "        \n",
    "        counts = 0\n",
    "        for s_key in s_count:\n",
    "            if s_count[s_key] % 2 == 1:\n",
    "                counts += 1\n",
    "        \n",
    "        if counts > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        c = Counter(s)\n",
    "        odd = 0\n",
    "        for v in c.values():\n",
    "            if v % 2 == 1:\n",
    "                odd += 1\n",
    "            if odd > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        odd = {}\n",
    "        \n",
    "        for ch in s:\n",
    "            if ch in odd.keys():\n",
    "                del odd[ch]\n",
    "            else:\n",
    "                odd[ch] = 0\n",
    "        if len(odd.keys()) > 1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in s:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        single_qty = 0\n",
    "        for v, k in dic.items():\n",
    "            if k % 2 == 1:\n",
    "                single_qty += 1\n",
    "                if single_qty > 1:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        l = [s.count(i) % 2 for i in set(s)]\n",
    "        if l.count(1) < 2:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "            if error > 1:\n",
    "                return False\n",
    "            \n",
    "        return (len(s) % 2 == 1 and error == 1) or (len(s) % 2 == 0 and error == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # s1=sorted(s)\n",
    "        l1=len(s)\n",
    "        s2=set(s)\n",
    "        count1=[]\n",
    "        count2=0\n",
    "        \n",
    "        for i in s2:\n",
    "            count1.append(s.count(i))\n",
    "        if l1%2==0:\n",
    "            for j in range(len(count1)):\n",
    "                if count1[j]%2!=0:\n",
    "                    return False\n",
    "                return True\n",
    "        else:\n",
    "            for j in range(len(count1)):\n",
    "                if count1[j]%2!=0:\n",
    "                    count2=count2+1\n",
    "            if count2>1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # 判断回文双指针,但是这道题本身指的是str的排列,不是str本身\n",
    "        # 所以从满足回文串的充要条件上出发, 如果是回文的.str长度\n",
    "        # 偶数的话, 所有字符出现的次数一定是偶数次\n",
    "        # 奇数的话, 所有字符出现的次数一定是偶数次, 加一个字符是奇数次\n",
    "        # hash\n",
    "        \n",
    "        # cac >>  caac  aab\n",
    "        s_dict = Counter(s)\n",
    "        odd_num = 0 # 初始化，记录频率次数是奇数的字符个数, 只记录这个就行了, 剩下的一定是偶数\n",
    "        for i,val in s_dict.items(): \n",
    "            if val%2!=0:\n",
    "                odd_num+=1\n",
    "            if odd_num > 1:  # 优化: 只要频率次是奇数的字符个数大于1,肯定F\n",
    "                return False\n",
    "        return True\n",
    "        # ou_num = len(s)-odd_num\n",
    "\n",
    "        # if len(s)%2==0: # str长度为偶数\n",
    "        #     if odd_num!=0:\n",
    "        #         return False\n",
    "        #     else:\n",
    "        #         return True\n",
    "        # else: # 奇数\n",
    "        #     if odd_num ==1:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        # if len(s)<= 2:\n",
    "        #     return True\n",
    "        a = Counter(s)\n",
    "        c =[]\n",
    "        for i in a.keys():\n",
    "            if a.get(i) %2 !=0:\n",
    "                c.append(i)\n",
    "        if len(c)>1:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        di = defaultdict(int)\n",
    "        for c in s:\n",
    "            if di[c] == 0:\n",
    "                di[c] += 1\n",
    "            else:\n",
    "                di[c] -= 1\n",
    "        count = 0\n",
    "        for n in di:\n",
    "            if di[n] != 0:\n",
    "                count += 1\n",
    "                if count > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        m = {}\n",
    "        for c in s:\n",
    "            m[c] = m.get(c,0) + 1\n",
    "        odd_count = 0\n",
    "        for c in m:\n",
    "            if m[c] % 2:\n",
    "                odd_count += 1\n",
    "        return odd_count <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(bool)\n",
    "        for c in s:\n",
    "            dic[c] = not dic[c]\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val is True:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "            if error > 1:\n",
    "                return False\n",
    "            \n",
    "        return (len(s) % 2 == 1 and error == 1) or (len(s) % 2 == 0 and error == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\"tactcoa\"\n",
    "\"code\"\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        # no more than one odd\n",
    "        odds = 0\n",
    "        for v in cnt.values():\n",
    "            if v % 2 != 0:\n",
    "                odds += 1\n",
    "            if odds > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        rs=0\n",
    "        for c in s:\n",
    "            rs ^= 1 << ord(c)\n",
    "        return rs & (rs-1) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        count = Counter(s)\n",
    "        ans = 0\n",
    "        for key, value in count.items():\n",
    "            if value%2 == 1:\n",
    "                ans += 1\n",
    "        return ans<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        \n",
    "        odd = 0\n",
    "        for value in dic.values():\n",
    "            if value % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        s=collections.Counter(s)\n",
    "        return sum(i%2!=0 for i in s.values())<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        tmp = {}\n",
    "        for c in s:\n",
    "            if c not in tmp:\n",
    "                tmp[c] = 1\n",
    "            else:\n",
    "                tmp[c] += 1\n",
    "        count = 0\n",
    "        for k in tmp:\n",
    "            if tmp[k] % 2 == 1:\n",
    "                count += 1\n",
    "        return count <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(bool)\n",
    "        for c in s:\n",
    "            d[c] = not d[c]\n",
    "        flag = False\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                flag = not flag\n",
    "                if flag is False:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        error = 0\n",
    "        count = {}\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count[ch] = 1\n",
    "            else:\n",
    "                count[ch] += 1\n",
    "        \n",
    "        for value in count.values():\n",
    "            if value & 1:\n",
    "                error += 1\n",
    "                if error > 1:\n",
    "                    return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(bool)\n",
    "        for c in s:\n",
    "            d[c] = not d[c]\n",
    "        flag = False\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                if flag:\n",
    "                    return False\n",
    "                flag = not flag\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "\n",
    "        dic = defaultdict(int)\n",
    "        for char in s:\n",
    "            dic[char] += 1\n",
    "        \n",
    "        odd_num = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd_num += 1\n",
    "                if odd_num == 2:\n",
    "                   return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        flag = False\n",
    "        for ch in cnt:\n",
    "            if cnt[ch] & 1:\n",
    "                if flag:\n",
    "                    return False\n",
    "                flag = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val % 2 == 1:\n",
    "                odd += 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        d = defaultdict(bool)\n",
    "        for c in s:\n",
    "            d[c] = not d[c]\n",
    "        flag = False\n",
    "        for v in d.values():\n",
    "            if v:\n",
    "                if flag:\n",
    "                    return False\n",
    "                flag = True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        arr = []\n",
    "        for ch in s:\n",
    "            if ch not in arr:\n",
    "                arr.append(ch)\n",
    "            else:\n",
    "                arr.pop(arr.index(ch))\n",
    "        return True if len(arr) <= 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        ret = 0\n",
    "        for c, n in Counter(s).items():\n",
    "            ret += n % 2\n",
    "        if ret > 1:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPermutePalindrome(self, s: str) -> bool:\n",
    "        dic = defaultdict(int)\n",
    "        for c in s:\n",
    "            dic[c] += 1\n",
    "        odd = 0\n",
    "        for val in dic.values():\n",
    "            if val%2 == 1:\n",
    "                odd+= 1\n",
    "                if odd > 1:\n",
    "                    return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
